#include <algorithm>
#include <iostream>
//
// Created by Asus on 2025/5/30.
//
using namespace std;

class SeqList {
private:
    // 顺序表存储的数组
    int *list;
    // 最大表长
    int maxsize;
    // 当前表长
    int size = 0;

    // 快速排序的分区函数
    int partition(int* arr, int low, int high);

    // 快速排序的递归函数 - 声明
    void quickSort(int* arr, int low, int high);

public:
    SeqList();

    ~SeqList();

    // 输入n个数，并依次存入顺序表从0开始的位置
    void list_int(int n);

    // 返回当前表长
    int getSize();

    int getSize2();

    // 把item插入到顺序表的第i个位置
    void insertItem(int i, int item);

    // 删除顺序表中的第i个数据
    void deleteItem(int i);

    // 打印顺序表中的第i个数据
    void printItem(int i);

    // 打印整个顺序表
    void showList();

    // 从i开始，连续插入来自item数组的n个数据
    void multiInsertItem(int i, int n, int *item);

    // 从i开始，将i及其之后的n个数据全部删除
    void multiDeleteItem(int i, int n);

    // 为顺序表内元素排序
    void sortList();

    // 返回数组
    int *getList();

    // 合并两个顺序表
    SeqList mergeList(SeqList &a, SeqList &b);

    // 循环排序，类似于abc往后移两位变成cba?
    void circleMoveList(int d, int n);
} seqlist;


// 构造函数
// 构造一个顺序表，最大的表长是maxsize，当前表的大小是0，内存中分配maxsize大小的空间
SeqList::SeqList() {
    maxsize = 100;
    size = 0;
    list = new int[maxsize];
}

// 析构函数
// 释放list数组的内存
SeqList::~SeqList() {
    delete[] list;
}

// 初始化顺序表
// 输入n个数，并依次存入顺序表从0开始的位置
void SeqList::list_int(int n) {
    for (int i = 0; i < n; ++i) {
        cin >> list[i];
        cout << list[i] << endl;
    }
    size = n;
}

int SeqList::getSize2() {
    return size;
}

// 返回当前表长
int SeqList::getSize() {
    for (int i = 0; i < maxsize; i++) {
        if (list[i] == '\0') {
            size = i + 1;
            break;
        }
    }
    return size;
}

// 把item插入到顺序表的第i个位置
void SeqList::insertItem(int i, int item) {
    if (i > 0 || i < size +1) {
        for (int k = size; k > i; --k) {
            list[k] = list[k - 1];
        }
        list[i-1] = item;
        size++;
    } else {
        cout << "error" << endl;
    }
}

// 删除顺序表中的第i个数据
void SeqList::deleteItem(int i) {
    if (i >= 1 || i <= size) {
        size--;
        for (int k = i-1; k < size; ++k) {
            list[k] = list[k + 1];
        }
    } else {
        cout << "error" << endl;
    }
}

// 打印指定元素
void SeqList::printItem(int i)
{
    // 条件和删除类似
    if (i > 0 && i <= size)
    {
        cout << list[i - 1] << endl;
    }
    else
        puts("不存在这个数据！");
}

// 打印整个顺序表
void SeqList::showList()
{
    cout << "该顺序表的表长是：" << size << endl;
    for (int i = 0; i < size; i++)
    {
        cout << list[i] << " ";
    }
    puts("");
}

// 从i开始，连续插入来自item数组的n个数据
void SeqList::multiInsertItem(int i, int n, int *item) {
    if (i > 0 && i < size +1) {
        for (int k = size + n - 1; k > i; --k) {
            list[k] = list[k - n];
        }
        for (int k = i - 1; k < i - 1 + n; k++) {
            list[k] = item[k-i+1];
        }
        size = size + n;
    } else {
        cout << "error" << endl;
    }
}

// 从i开始，将i及其之后的n个数据全部删除
void SeqList::multiDeleteItem(int i, int n)
{
    // TODO: 添加一个条件，i 之后的 n个元素是否会超出maxsize
    // 条件类似删除单个元素
    if (i > 0 && i <= size)
    {
        size -= n; // 删除了n个元素，size就要减n
        // 从第i个开始（数组下标的i - 1），依次将n个之后的数据向前挪n位
        for (int k = i - 1; k < size; k++)
        {
            list[k] = list[k + n];
        }
    }
    else
        puts("删除元素错误！");
}

void SeqList::sortList() {
    quickSort(list, 0, size - 1);
}

// 快速排序的递归函数
void SeqList::quickSort(int* arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);

        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

// 快速排序的分区函数
int SeqList::partition(int* arr, int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; ++j) {
        if (arr[j] <= pivot) {
            ++i;
            std::swap(arr[i], arr[j]);
        }
    }
    std::swap(arr[i + 1], arr[high]);
    return i + 1;
}

// 返回数组
int *SeqList::getList()
{
    return list; // 数组名相当于指针
}

// 合并两个顺序表
SeqList SeqList::mergeList(SeqList &a, SeqList &b)
{
    SeqList res;
    // 相当于把两个表分别插入res表
    res.multiInsertItem(0, a.getSize(), a.getList()); // 先插入a，从零开始，长度为a的长度，分别将a的元素插入res中
    res.multiInsertItem(a.getSize() + 1, b.getSize(), b.getList());
    // res.sortList();           //按需为新表排序
    return res;
}

// 顺序表循环移位
void SeqList::circleMoveList(int d, int n) // 每个向后移n位，d代表方向，0为左、1为右
{
    // 先创造一个临时的表，先把原表复制到临时表里，然后按照规律把临时表里的数据赋给原表，最后记得把临时表释放
    // 创建临时表
    int *temp = new int[size];
    // 原表复制给临时表
    temp = list;
    // 按照规律赋值
    if (d == 0) // 左移
    {
        for (int i = 0; i < size - n; i++)
        {
            list[i] = temp[i + n]; // 因为是往左移，所以是右边的把左边的给覆盖掉，直到size - n为止，因为temp的前n个被移到末尾去了
        }
        for (int i = size - n; i < size; i++)
        {
            list[i] = temp[i - (size - n)]; // 其实就是temp的前n个赋给list的后n个
        }
    }
    // 释放临时表
    delete[] temp;
}